package leecode

import "sort"

func minSetSize(arr []int) int {
	hashMap := make(map[int]int)
	for _, num := range arr {
		hashMap[num]++
	}
	count := make([]int, 0)
	for _, value := range hashMap {
		count = append(count, value)
	}
	sort.Ints(count)
	var result int
	temp := 0
	for i := len(count) - 1; i >= 0; i-- {
		temp = temp + count[i]
		if len(arr)-temp > len(arr)/2 {
			result++
		} else {
			break
		}
	}
	return result + 1
}
